package main

import (
	"errors"
	"fmt"
	"strconv"
)

type Node struct {
	item int
	next *Node
	prev *Node
}

func (n *Node) String() string {
	var next, prev string
	if n.next == nil {
		next = "null"
	} else {
		next = strconv.Itoa(n.next.item)
	}

	if n.prev == nil {
		prev = "null"
	} else {
		prev = fmt.Sprintf("%d", n.prev.item)
	}

	return fmt.Sprintf(
		"%s <== %d ==> %s",
		prev,
		n.item,
		next,
	)
}

type LinkedList struct {
	head *Node
	tail *Node
	len  int
}

func New() *LinkedList {
	return &LinkedList{}
}

func (l *LinkedList) Len() int {
	return l.len
}

func (l *LinkedList) Append(item int) {
	node := new(Node)
	node.item = item

	if l.head == nil {
		l.head = node
		l.tail = node
	} else {
		l.tail.next = node
		node.prev = l.tail
		l.tail = node
	}

	l.len++
}

func (l *LinkedList) Pop() error {
	if l.tail == nil {
		return errors.New("Empty")
	} else if l.head == l.tail {
		l.head = nil
		l.tail = nil
	} else {
		tail := l.tail
		prev := tail.prev
		prev.next = nil
		l.tail = prev
	}
	l.len--
	return nil
}

func (l *LinkedList) Insert(index int, value int) error {
	if index < 0 {
		return errors.New("Not negaive")
	}
	var current *Node
	var flag bool
	for i, v := range l.IterNodes(false) {
		if i == index {
			current = v
			flag = true
			break
		}
	}
	if !flag {
		l.Append(value)
		return nil
	}

	node := new(Node)
	node.item = value

	prev := current.prev
	if index == 0 {
		l.head.prev = node
		node.next = l.head
	} else {
		prev.next = node
		node.prev = prev
	}
	node.next = current
	current.prev = node

	l.len++
	return nil
}

func (l *LinkedList) Remove(index int) error {
	if l.tail == nil {
		return errors.New("Entry")
	}

	if index < 0 {
		return errors.New("Not negative")
	}
	var current *Node
	var flag bool
	for i, v := range l.IterNodes(false) {
		if i == index {
			current = v
			flag = true
			break
		}
	}
	if !flag {
		return errors.New("out")
	}
	prev := current.prev
	next := current.next

	if prev == nil && next == nil {
		l.head = nil
		l.tail = nil
	} else if prev == nil {
		l.head = next
		next.prev = nil
	} else if next == nil {
		prev.next = nil
		l.tail = prev
	} else {
		prev.next = next
		next.prev = prev
	}
	l.len--
	return nil

}

func (l *LinkedList) IterNodes(reversed bool) []*Node {
	var p *Node
	r := make([]*Node, 0, l.len)
	if reversed {
		p = l.tail
	} else {
		p = l.head
	}

	for p != nil {
		// fmt.Println(p)
		r = append(r, p)
		if reversed {
			p = p.prev
		} else {
			p = p.next
		}
	}
	return r
}

func main() {
	ll := New()
	ll.Append(2)
	ll.Append(3)
	ll.Insert(0, 0)
	ll.Insert(1, 1)
	ll.Append(5)
	ll.Insert(4, 4)
	fmt.Println(ll.IterNodes(false))
	ll.Remove(1)
	fmt.Println(ll.IterNodes(false))
	ll.Pop()
	fmt.Println(ll.IterNodes(false))
}
